import java.util.HashMap;
import java.util.Map;

import org.w3c.dom.Node;

/*
 * @lc app=leetcode.cn id=138 lang=java
 *
 * [138] 复制带随机指针的链表
 *
 * https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/
 *
 * algorithms
 * Medium (41.02%)
 * Likes:    169
 * Dislikes: 0
 * Total Accepted:    16.8K
 * Total Submissions: 40.2K
 * Testcase Example:  '[[7,null],[13,0],[11,4],[10,2],[1,0]]\r'
 *
 * 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
 *
 * 要求返回这个链表的 深拷贝。 
 *
 * 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
 *
 *
 * val：一个表示 Node.val 的整数。
 * random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
 *
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 *
 * 示例 2：
 *
 *
 *
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 *
 *
 * 示例 3：
 *
 *
 *
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 *
 *
 * 示例 4：
 *
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *
 *
 *
 *
 * 提示：
 *
 *
 * -10000 <= Node.val <= 10000
 * Node.random 为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 *
 *
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    Map<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        return copy(head);
    }

    Node copy(Node head) {
        if(head == null) {
            return head;
        }
        Node cur = head;
        while(cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while(cur != null && cur.next != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        Node root = head.next;
        Node src = head, dst = root;
        while(src != null) {
            src.next = dst.next;
            dst.next = dst.next == null ? null : dst.next.next;
            src = src.next;
            dst = dst.next;
        }
        return root;
    }


    //字典存储
    Node fun(Node head) {
        if(head == null) {
            return head;
        }
        Node node = head;
        Node copy = null;
        while(node != null) {
            copy = getNode(node);
            copy.next = getNode(node.next);
            copy.random = getNode(node.random);
            node = node.next;
            copy = copy.next;
        }

        return getNode(head);
    }

    Node getNode(Node node) {
        if(node == null)
            return null;
        if(!this.map.containsKey(node)) {
            this.map.put(node, new Node(node.val));
        }
        return this.map.get(node);
    }
}
// @lc code=end

